\documentclass{beamer}
\usepackage{graphicx}				%
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{algorithmic}
\usepackage{hyperref}
\usepackage{float}
\usepackage{appendix}
\usepackage{multicol}
\usepackage{cite}
\usepackage{url}
\usepackage{enumerate}
\usepackage{clrscode}

\hypersetup{
   bookmarks=true,         				% show bookmarks bar?
   unicode=false,          				% non-Latin characters in AcrobatÕs bookmarks
   pdftoolbar=true,        				% show AcrobatÕs toolbar?
   pdfmenubar=true,      				% show AcrobatÕs menu?
   pdffitwindow=true,      				% page fit to window when opened
   pdftitle={},    	% title
   pdfauthor={Paul Romanczyk},     		% author
   pdfsubject={},
   pdfnewwindow=true,      				% links in new window
   pdfkeywords={}, 	% list of keywords
   colorlinks=true,       				% false: boxed links; true: colored links
   linkcolor=red,          				% color of internal links
   citecolor=green,        				% color of links to bibliography
   filecolor=magenta,      				% color of file links
   urlcolor=cyan           				% color of extern 
}


% \usepackage{beamerthemesplit} // Activate for custom appearance
\usetheme{Marburg}


%%% Use \graphicspath{{pngs/}} for choosing a good example and use \graphicspath{{Figures/}} for the final presentation  %%%

%\graphicspath{{Figures/}}
\graphicspath{{pngs/}}

\title[Agglomerative Hierarchical Clustering\hspace{2em}10/14/2010\hspace{3em}	\insertframenumber]{Agglomerative Hierarchical Clustering}
\author[Loomis \& Romanczyk]{James Loomis \& Paul Romanczyk}
\date{October 27, 2010}

\begin{document}

\frame{\titlepage}

\section[Outline]{Outline}
\frame
{
\frametitle{Outline}
\tableofcontents
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%     Introduction
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\begin{frame}
\frametitle{Hierarchical Clustering}
Hierarchical clustering:
	\begin{itemize}
	\item Clustering using a hierarchy of clusters 
	\item May be represented in a tree structure \emph{(dendrogram)}
	\item Root - a single cluster containing all observations
	\item Leaves - individual observations.
	\end{itemize}

	\pause \includegraphics[scale=.43]{venn.pdf}
\end{frame}

\begin{frame}
	\frametitle{Dendrogram}
	
	\includegraphics[scale=.5]{dendrogram.png} \\
	\emph{\cite{dhs} Figure 10.11}	
\end{frame}


\begin{frame}
	\begin{itemize}
		\item[]Two Distinct Approaches: 
		\pause 
		\item Agglomerative \emph{(bottom up, clumping)}
			\begin{itemize}
				\item Start with $n$ \emph{singleton} clusters
				\item Successively merge \emph{("clump")} clusters
				\item Computation from one level to another generally simpler
				\item For small number of clusters, takes many iterations
			
			\end{itemize}
		\pause
		\item Divisive \emph{(top down, splitting)}
			\begin{itemize} 
				\item Start with one cluster
				\item Successively split clusters
				\item Single iteration is more expensive
				\item With fewer clusters, fewer iterations
			
			\end{itemize}
	\end{itemize}
\end{frame}
\begin{frame}

	\frametitle{Agglomerative Clustering Algorithm}
	\begin{codebox}
		\li $c, \hat{c} \gets n$
		\li $D_i \gets \{ \mathbf{x}_i \}$ \textbf{where} $i = 1, \ldots, n$ 
		\zi
		\li \Do $\hat{c} \gets \hat{c} - 1$
		\li find \emph{nearest} clusters $D_i$, $D_j$
		\li merge $D_i$ and $D_j$
		\li \Until $c = \hat{c}$
		\zi
		\li \Return $c$ clusters
		
		
	\end{codebox}

	\pause
	How do we determine which two clusters are \emph{nearest}?
	
\end{frame}


\section{Distance}
\begin{frame}
	\frametitle{Properties of Distance} 
	\begin{itemize}
		\item Distance is non-negative. 
		\begin{itemize}
			\item $D(x,y)\ge0$
		\end{itemize}
		\item $D(x,y)=0$ if and only if $x=y$.
		\item Distance is symmetric.
		\begin{itemize}
			\item $D(x,y)=D(y,x)$
		\end{itemize}
		\item Distance satisfies the triangle inequality 
		 \begin{itemize}
			\item $D(x,z)\le D(x,y)+D(y,z)$
		\end{itemize}
	\end{itemize}
\end{frame}
\begin{frame}
	\frametitle{Distance Measures---Between Points} 
	Let $\vec{x_1}=[\begin{array}{cccc}x_{1,1}&x_{1,2}&\cdots&x_{1,n}\end{array}]^T$ and $\vec{x_2}=[\begin{array}{cccc}x_{2,1}&x_{2,2}&\cdots&x_{2,n}\end{array}]^T$\\
	\vspace{0.1in}
	
	\begin{tabular}{l|l}
		Name & Formula \\ \hline
		Manhattan & $d_1(\vec{x_1},\vec{x_2})=\sum_{i=1}^n\left|x_{1,i}-x_{2,i}\right|$\\
		Euclidian & $d_2(\vec{x_1},\vec{x_2})=\sqrt{\sum_{i=1}^n\left|x_{1,i}-x_{2,i}\right|^2}$\\
		P-norm & $d_p(\vec{x_1},\vec{x_2})=\sqrt[p]{\sum_{i=1}^n\left|x_{1,i}-x_{2,i}\right|^p}$\\
		Statistical & $d_s(\vec{x_1},\vec{x_2})=\sqrt{\sum_{i=1}^n\left(\frac{x_{1,i}-x_{2,i}}{\sigma_i}\right)^2}$\\
		Mahalanobis &  $d_m(\vec{x_1},\vec{x_2})=\sqrt{(\vec{x_1}-\vec{\mu})\Sigma^{-1}(\vec{x_2}-\vec{\mu})^T}$\\
		Cosine & $d_c(\vec{x_1},\vec{x_2})=\frac{\vec{x_1}^T\vec{x_1}}{||\vec{x_2}||\cdot||\vec{x_2}||}$\\
		Chebyshev & $d_C(\vec{x_1},\vec{x_2})=\max(|x_{1,i}-x_{2,i}|)$\\
	\end{tabular}
\end{frame}
\begin{frame}
	\frametitle{Distance Measures---Between Clusters} 
	\begin{tabular}{c|c}
		\textbf{Single Linkage}&$d_{(U,V),W}=\min\{d_{U,W},d_{V,W}\}$\\ \hline
		$d_{2,4}$&\includegraphics[scale=0.5]{singleLinkage}\\ \hline \hline
		\textbf{Complete Linkage}&$d_{(U,V),W}=\max\{d_{U,W},d_{V,W}\}$\\ \hline
		$d_{1,5}$&\includegraphics[scale=0.5]{totalLinkage}\\ \hline \hline
		\textbf{Average Linkage}&$d_{(U,V),W}=\frac{\displaystyle\sum_{i}\sum_{j} d_{i,j}}{N_{U,V}N_W}$\\ \hline
		$\frac{\displaystyle\sum_{i=1}^2\sum_{j=3}^5 d_{i,j}}{2\cdot3}$&\includegraphics[scale=0.5]{averageLinkage}\\ 
	\end{tabular}
\end{frame}

\section{Example}

\include{data}
\subsection[S.L. Dist. Matrices]{Single Linkage Distance Matrices} 
\include{Stables}
\subsection{Cluster Plots}
\include{incFig}
\subsection[Dendrodgrams]{Dendrograms}
\begin{frame}
	\frametitle{Example--Single Linkage Dendrogram}
	\includegraphics[scale=0.5]{DS}
\end{frame}
\begin{frame}
	\frametitle{Example--Total Linkage Dendrogram}
	\includegraphics[scale=0.5]{DT}
\end{frame}
\begin{frame}
	\frametitle{Example--Average Dendrogram}
	\includegraphics[scale=0.5]{DA}
\end{frame}
\begin{frame}
	\frametitle{Example--Dendrogram}
	\includegraphics[height=0.25\textheight, width=1\textwidth]{DS2}\\
	\includegraphics[height=0.25\textheight, width=1\textwidth]{DT2}\\
	\includegraphics[height=0.25\textheight, width=1\textwidth]{DA2}\\
	\tiny
	\textcolor{red}{Single Linkage} \textcolor{green}{Complete Linkage} \textcolor{blue}{Average Linkage}
	\normalsize
\end{frame}


\subsection{Summary}
\include{results}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%    References
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{References}
\frame
{
	\frametitle{References}
	\nocite{*}
	\bibliographystyle{apalike}
	\bibliography{ref}
}

\section{Questions}
\frame
{
	\frametitle{Questions}
}

\section{Extra Stuff}
\subsection[T.L. Dist. Matrices]{Total Linkage Distance Matrices} 
\include{Ttables}
\subsection[A.L. Dist. Matrices]{Average Linkage Distance Matrices} 
\include{Atables}


%\begin{frame}[fragile]
%	\frametitle{}
%	\begin{itemize}
%		\item \textcolor{blue}{blue text}
%	\end{itemize}
%\end{frame}

\end{document}

